package nachos.threads;

import nachos.machine.*;

import java.util.TreeSet;
import java.util.HashSet;
import java.util.Iterator;

/**
 * 使用抽签选择线程的调度程序
 * <p>
 * 彩票调度器将多张彩票与每个线程相关联
 * 当一个线程需要退出队列时，将在等待退出队列的所有线程的所有票证中举行随机抽签
 * 持有中奖彩票的线程被选中
 * <p>
 * 请注意，彩票调度器必须能够处理大量彩票（有时是数十亿张），因此不能为每张彩票维护状态
 * <p>
 * 彩票调度器必须部分解决优先级反转问题
 * 特别是，票证必须通过锁和 join 进行传输
 * 与优先级调度器不同，这些票证会取加和（而不是只获取最大值）
 */
public class LotteryScheduler extends PriorityScheduler {
    /**
     * 分配一个新的彩票调度程序
     */
    public LotteryScheduler() {
    }

    /**
     * 分配一个新的彩票线程队列
     *
     * @param transferPriority true 如果此队列应该将票据从等待的线程转移到拥有的线程
     * @return 一个新的彩票线程队列
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
        return new LotteryQueue(transferPriority);
    }

    protected ThreadState getThreadState(KThread thread) {
        if (thread.schedulingState == null)
            thread.schedulingState = new LotteryThreadState(thread);

        return (ThreadState) thread.schedulingState;
    }

    protected class LotteryQueue extends PriorityQueue {
        LotteryQueue(boolean transferPriority) {
            super(transferPriority);
        }

        protected ThreadState pickNextThread() {
            // 计算彩票总数
            int lotterySum = 0;
            for (ThreadState lotteryThreadState : list) {
                if (transferPriority) {
                    lotterySum += lotteryThreadState.getEffectivePriority();
                } else {
                    lotterySum += lotteryThreadState.getPriority();
                }

            }

            // 当前存在可运行的线程
            if (lotterySum != 0) {
                // 指定获胜彩票
                int winLottery = Lib.random(lotterySum) + 1;

                // 当前彩票计数
                int currentLotteryNum = 0;

                // 遍历所有线程，直到找到持有中奖彩票的线程
                for (ThreadState lotteryThreadState: list) {
                    if (transferPriority) {
                        currentLotteryNum += lotteryThreadState.getEffectivePriority();
                    } else {
                        currentLotteryNum += lotteryThreadState.getPriority();
                    }

                    // 找到获奖彩票
                    if (currentLotteryNum >= winLottery) {
                        return lotteryThreadState;
                    }
                }
            }

            return null;
        }
    }

    protected class LotteryThreadState extends ThreadState {
        public LotteryThreadState(KThread thread) {
            super(thread);
        }

        public int getEffectivePriority() {
            // 尝试使用之前保存的数据
            if (KThread.getPriorityStatus()) {
                return effectivePriority;
            }

            // 重新计算有效优先级
            effectivePriority = priority;

            // 遍历该线程的等待线程列表
            for (KThread waitThread : thread.getWaitThreadList()) {
                // 等待线程的有效优先级
                effectivePriority += getThreadState(waitThread).getEffectivePriority();
            }

            return effectivePriority;
        }
    }
}
